/*
Algorithms:  brief Definition of algorithms classes from fui.
    Copyright (C) 2012  Jorge E. A. Atala
                        FuDePAN
    This file is part of the Fui Proyect.

    Fui is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Fui is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Fui.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef ALGORITHMS_H
#   define ALGORITHMS_H
#   include<algorithm>
#   include <iterator>
namespace fui
{
/*! \addtogroup Algorithms
 *  \{
 */

/*! \p reduce is a generalization of summation: it computes the sum of all the
 *  elements in the range <tt>[first,last)</tt>. This version of \p reduce
 *  uses \c 0 as the initial value of the reduction.
 *  \p reduce requires associativity of the binary operation to parallelize
 *  the reduction.
 *
 *  Note that \p reduce also assumes that the binary reduction operator (in this
 *  case operator+) is commutative.  If the reduction operator is not commutative
 *  then \p fui::reduce should not be used.
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \return The result of the reduction.
 *
 *  The following code snippet demonstrates how to use \p reduce to compute
 *  the sum of a sequence of integers.
 *
 *  \code
 *  ...
 *  int data[6] = {1, 0, 2, 2, 1, 3};
 *  int result = fui::reduce(data, data + 6);
 *
 *  // result == 9
 *  \endcode
 *
 */
template<class InputIterator >
typename std::iterator_traits<InputIterator>::value_type reduce(InputIterator first, const InputIterator& last)
{
    typedef typename std::iterator_traits<InputIterator>::value_type Element;
    Element sum(0);
    for (; first != last; ++first)
        sum += *first;
    return sum;
}

/*! \p reduce is a generalization of summation: it computes the sum of all the
 *  elements in the range <tt>[first,last)</tt>. This version of \p reduce
 *  uses \p init as the initial value of the reduction.
 *  \p reduce requires associativity of the binary operation to parallelize
 *  the reduction.
 *
 *  Note that \p reduce also assumes that the binary reduction operator (in this
 *  case operator+) is commutative.  If the reduction operator is not commutative
 *  then \p fui::reduce should not be used.
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \param init The initial value of the reduction.
 *  \return The result of the reduction.
 *
 *  The following code snippet demonstrates how to use \p reduce to compute
 *  the sum of a sequence of integers.
 *
 *  \code
 *  ...
 *  int data[6] = {1, 0, 2, 2, 1, 3};
 *  int result = fui::reduce(data, data + 6,11);
 *
 *  // result == 20
 *  \endcode
 *
 */
template<class InputIterator >
typename std::iterator_traits<InputIterator>::value_type reduce(InputIterator first,
        const InputIterator& last,
        typename std::iterator_traits<InputIterator>::value_type init)
{
    for (; first != last; ++first)
        init += *first;
    return init;
}

/*! \p This version of reduce performs a binary operation recursively with all
 *  the elements in the range <tt>[first,last)</tt>.
 *  \p reduce requires associativity of the binary operation to parallelize
 *  the reduction.
 *
 *  Note that \p reduce also assumes that the binary reduction operator is
 *  commutative. If the reduction operator is not commutative then
 *  \p fui::reduce should not be used.
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \param init The initial value for the reduction.
 *  \param op The binary operation for the reduction.
 *  \return The result of the reduction.
 *
 *  The following code snippet demonstrates how to use \p reduce to compute
 *  the sum of a sequence of integers.
 *
 *  \code
 *  ...
 *  struct MultiplyOperation
 *  {
 *      __host__ __device__
 *      int operator()(int a, int b)
 *      {
 *          return a * b;
 *      }
 *  };
 *
 *
 *  int data[6] = {1, 1, 2, 2, 1, 3};
 *  int result = fui::reduce(data, data + 6,MultiplyOperation());
 *
 *  // result == 12
 *  \endcode
 *
 */
template<class InputIterator , class BinaryFunction>
typename std::iterator_traits<InputIterator>::value_type reduce(InputIterator first,
        const InputIterator& last,
        typename std::iterator_traits<InputIterator>::value_type init,
        BinaryFunction& op)
{
    for (; first != last; ++first)
        init = op(init, *first);
    return init;
}

/*! \p This version of transform perform one operation for each element
 *  in a range <tt>[first,last)</tt> and put the elements resultants in
 *  the result parameter.
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \param result The beginning of the result sequence.
 *  \param op The unary function uses for perform the transformation.
 *  \return The end of the result sequence, that could not be thereal end
 *  of the original sequence if the input sequence was more short than the result one.
 *
 *  The following code snippet demonstrates how to use \p transform to compute
 *  the sum of 10 for each element in the input range.
 *
 *  \code
 *  ...
 *  struct PlusOperation
 *  {
 *      __host__ __device__
 *      int operator()(int a)
 *      {
 *          return a + 10;
 *      }
 *  };
 *
 *
 *  fui::device_vector<int>::type data1(6,1);
 *  fui::device_vector<int>::type result(6);
 *  fui::transform(data1.begin(), data1.end(), result, PlusOperation());
 *
 *  // result == {11,11,11,11,11,11}
 *  \endcode
 *
 */
template<class InputIterator , class OutputIterator , class UnaryFunction >
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op)
{
    while (first != last)
    {
        *result = op(*first);
        ++first;
        ++result;
    }
    return result;
}

/*! \p This version of transform perform one binary operation for each element
 *  with the same index in two inputs ranges <tt>[first,last)</tt> and put
 *  the elements resultants in the result parameter.
 *
 *  \param first1 The beginning of the first sequence.
 *  \param last1 The end of the first sequence.
 *  \param first2 The beginning of second the sequence.
 *  \param result The beginning of the result sequence.
 *  \param op The binary function uses for perform the transformation.
 *  \return The end of the result sequence, that could not be thereal end
 *  of the original sequence if the input sequence was more short than the result one.
 *
 *  The following code snippet demonstrates how to use \p transform to compute
 *  the sum of each pair of elements from the two vectors.
 *
 *  \code
 *  struct PlusOperation
 *  {
 *      __host__ __device__
 *      int operator()(int a,int b)
 *      {
 *          return a + b;
 *      }
 *  };
 *
 *
 *  fui::device_vector<int>::type data1(6,1);
 *  fui::device_vector<int>::type data2(6,8);
 *  fui::device_vector<int>::type result(6);
 *  fui::transform(data1.begin(), data1.end(), data2.begin(), result, PlusOperation());
 *
 *  // result == {9,9,9,9,9,9}
 *  \endcode
 *
 */
template<class InputIterator1 , class InputIterator2 , class OutputIterator , class BinaryFunction >
OutputIterator transform(InputIterator1 first1, const InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction op)
{
    while (first1 != last1)
    {
        *result = op(*first1, *first2);
        ++first1;
        ++first2;
        ++result;
    }
    return result;
}

/*! \p find returns an iterator to the first element in the
 *  range <tt>[first,last)</tt> that compares equal to value, or last if not found
 *
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \param value The value to find in the range.
 *  \return The iterator to the value in the range, or last if not found.
 *
 *  The following code snippet demonstrates how to use the \p find algorithm.
 *
 *  \code
 *  ...
 *
 *  int data[6] = {1, 0, 2, 2, 1, 3};
 *  int* it = fui::find(data, data + 6,2);
 *
 *  // *result == 2 // The first appareance
 *  \endcode
 *
 */
using std::find;

/*! \p find_if returns an iterator to the first element in the
 *  range <tt>[first,last)</tt> for the result of application of op is True.
 *
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \param op The boolean unary operation for test each element.
 *  \return The iterator to the first element in the range that computes
 *  True with the operand, or last if all computes false.
 *
 *  The following code snippet demonstrates how to use the \p find__if algorithm
 *
 *  \code
 *  ...
 *  struct MoreThanOne
 *  {
 *      __host__ __device__
 *      bool operator()(int a)const
 *      {
 *          return (a > 1);
 *      }
 *  };
 *
 *  int data[6] = {1, 0, 2, 2, 1, 3};
 *  int* it = fui::find(data, data + 6,2,MoreThanOne());
 *
 *  // *result == 2 // The first appareance
 *  \endcode
 *
 */
using std::find_if;

/*! \p This version of mismatch returns an iterator to the first pair of
 *  elements in the ranges <tt>[first1,last1)</tt> and
 *  <tt>[first2,first2 + last1 - first1)</tt> in the two entry vectors that differs.
 *
 *
 *  \param first1 The beginning of the sequence.
 *  \param last1 The end of the sequence.
 *  \param first1 The beginning of the sequence.
 *  \return The pair of elements that differ, if the different elements don't exist,
 *  then return the pair <tt>(*last1, *(first2 + last1 - first1))</tt>.
 *
 *  The following code snippet demonstrates how to use the \p find__if algorithm
 *
 *  \code
 *  ...
 *
 *  int data1[6] = {1, 0, 2, 2, 1, 3};
 *  int data2[6] = {1, 0, 2, 9, 1, 3};
 *  fui::pair<*int,*int> result = fui::mismatch(data1, data1 + 6, data2);
 *
 *  // result == (data1 + 3, data2 + 3) //(2,9)
 *  \endcode
 *
 */
/*for mismatch*/

/*! \p This version of mismatch returns an iterator to the first pair of
 *  elements in the ranges <tt>[first1,last1)</tt> and
 *  <tt>[first2,first2 + last1 - first1)</tt> in the two entry vectors that the
 *  result to do the operation op with the two elements with the same index returs
 *  false.
 *
 *
 *  \param first1 The beginning of the sequence.
 *  \param last1 The end of the sequence.
 *  \param first1 The beginning of the sequence.
 *  \param op The boolean unary operation for test each pair of element.
 *  \return The pair of elements that differ, if the different elements don't exist,
 *  then return the pair <tt>(*last1, *(first2 + last1 - first1))</tt>.
 *
 *  The following code snippet demonstrates how to use the \p find__if algorithm
 *
 *  \code
 *  ...
 *  struct TheSumIsPair
 *  {
 *      __host__ __device__
 *      bool operator()(int a, int b)const
 *      {
 *          return (a + b) % 2 == 0;
 *      }
 *  };
 *
 *  int data1[6] = {1, 0, 2, 2, 1, 3};
 *  int data2[6] = {1, 0, 2, 9, 1, 3};
 *  fui::pair<*int,*int> result = fui::mismatch(data1, data1 + 6, data2, TheSumIsPair());
 *
 *  // result == (data1 + 3, data2 + 3) //(2,9)
 *  \endcode
 *
 */
using std::mismatch;

/*! \p partition reorders the elements <tt>[first, last)</tt> based on the function
 *  object op, such that all of the elements that satisfy op precede the elements
 *  that fail to satisfy it. The postcondition is that, for some iterator middle
 *  in the range <tt>[first, last)</tt>, <tt>op(*i)</tt> is true for every
 *  iterator <tt>i</tt> in the range <tt>[first,middle)</tt> and false for every
 *  iterator <tt>i</tt> in the range <tt>[middle, last)</tt>.
 *  The return value of partition is middle.
 *
 *  Note that the relative order of elements in the two reordered sequences is not
 *  necessarily the same as it was in the original sequence. A different algorithm,
 *  \p stable_partition, does guarantee to preserve the relative order.
 *
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \param op The boolean unary operation for test each pair of element.
 *  \return The pair of elements that differ, if the different elements don't exist,
 *  then return the pair <tt>(*last1, *(first2 + last1 - first1))</tt>.
 *
 *  The following code snippet demonstrates how to use the \p find__if algorithm
 *
 *  \code
 *  ...
 *  struct IsPair
 *  {
 *      __host__ __device__
 *      bool operator()(int a)const
 *      {
 *          return a % 2 == 0;
 *      }
 *  };
 *
 *  int data[6] = {1, 0, 2, 2, 1, 3};
 *  *int result = fui::partition(data1, data1 + 6, IsPair());
 *
 *  // result == (data1 + 3)
 *  // data = {0, 2, 2, 1, 1, 3}
 *  \endcode
 *
 */
using std::partition;

/*! \p stable_partition reorders the elements <tt>[first, last)</tt> based on the function
 *  object op, such that all of the elements that satisfy op precede the elements
 *  that fail to satisfy it. The postcondition is that, for some iterator middle
 *  in the range <tt>[first, last)</tt>, <tt>op(*i)</tt> is true for every
 *  iterator <tt>i</tt> in the range <tt>[first,middle)</tt> and false for every
 *  iterator <tt>i</tt> in the range <tt>[middle, last)</tt>.
 *  The return value of partition is middle.
 *
 *  Note that the relative order of elements in the two reordered sequences is
 *  the same as it was in the original sequence. This is the difference with
 *  the algorithm \p partition, does not guarantee to preserve the relative order.
 *
 *
 *  \param first The beginning of the sequence.
 *  \param last The end of the sequence.
 *  \param op The boolean unary operation for test each pair of element.
 *  \return The pair of elements that differ, if the different elements don't exist,
 *  then return the pair <tt>(*last1, *(first2 + last1 - first1))</tt>.
 *
 *  The following code snippet demonstrates how to use the \p find__if algorithm
 *
 *  \code
 *  ...
 *  struct IsPair
 *  {
 *      __host__ __device__
 *      bool operator()(int a)const
 *      {
 *          return a % 2 == 0;
 *      }
 *  };
 *
 *  int data[6] = {1, 0, 2, 2, 1, 3};
 *  *int result = fui::partition(data1, data1 + 6, IsPair());
 *
 *  // result == (data1 + 3)
 *  // data = {0, 2, 2, 1, 1, 3}
 *  \endcode
 *
 */
using std::stable_partition;

using std::remove;
using std::remove_copy;
using std::remove_if;
using std::unique;
using std::unique_copy;
using std::swap_ranges;


class Combinator
{

protected:

    size_t summatoria(size_t n)
    {
        size_t result = n;
        while (n != 0)
            result += --n;
        return result;
    }

public:
    Combinator() {}

    /*    template<class InputIterator, class OutputIterator , class CombinatorialFunction>
        void combinationsWithoutReposition(InputIterator begin,
                                           const InputIterator end,
                                           OutputIterator output,
                                           CombinatorialFunction.
                                           const unsigned int combinations)
        {


        }

        template<class InputIterator, class OutputIterator , class CombinatorialFunction>
        void combinationsWithoutReposition(InputIterator begin,
                                           const InputIterator end,
                                           OutputIterator output,
                                           CombinatorialFunction.
                                           const unsigned int combinations)
        {


        }
    */

};

/*!
 * \}
 */
}
#endif











